package com.lw.leetcode.dp.c;

/**
 * Created with IntelliJ IDEA.
 * c
 * dp
 * 960. 删列造序 III
 *
 * @author liw
 * @version 1.0
 * @date 2023/2/1 14:14
 */
public class MinDeletionSize {

    public static void main(String[] args) {
        MinDeletionSize test = new MinDeletionSize();

        // 3
//        String[] strs = {"babca", "bbazb"};

        // 4
//        String[] strs = {"edcba"};

        // 2
        String[] strs = {"baabab"};

        // 0
//        String[] strs = {"ghi", "def", "abc"};

        int i = test.minDeletionSize(strs);
        System.out.println(i);
    }

    public int minDeletionSize(String[] strs) {
        int m = strs.length;
        int n = strs[0].length();
        char[][] arr = new char[m][n];
        int[] counts = new int[n];
        for (int i = 0; i < m; i++) {
            arr[i] = strs[i].toCharArray();
        }
        int max = 0;
        for (int i = 1; i < n; i++) {
            for (int j = i - 1; j >= 0; j--) {
                boolean f = true;
                for (int k = 0; k < m; k++) {
                    if (arr[k][i] < arr[k][j]) {
                        f = false;
                        break;
                    }
                }
                if (f) {
                    counts[i] = Math.max(counts[i], counts[j] + 1);
                }
            }
            max = Math.max(max, counts[i]);
        }
        return n - max - 1;
    }

}
